home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / indep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  2.9 KB  |  126 lines  |  [TEXT/R*ch]
  1. #include "mincov_int.h"
  2.  
  3. static sm_matrix *build_intersection_matrix();
  4.  
  5.  
  6. #if 0
  7. /*
  8.  *  verify that all rows in 'indep' are actually independent !
  9.  */
  10. static int 
  11. verify_indep_set(A, indep)
  12. sm_matrix *A;
  13. sm_row *indep;
  14. {
  15.     register sm_row *prow, *prow1;
  16.     register sm_element *p, *p1;
  17.  
  18.     for(p = indep->first_col; p != 0; p = p->next_col) {
  19.     prow = sm_get_row(A, p->col_num);
  20.     for(p1 = p->next_col; p1 != 0; p1 = p1->next_col) {
  21.         prow1 = sm_get_row(A, p1->col_num);
  22.         if (sm_row_intersects(prow, prow1)) {
  23.         return 0;
  24.         }
  25.     }
  26.     }
  27.     return 1;
  28. }
  29. #endif
  30.  
  31. solution_t * 
  32. sm_maximal_independent_set(A, weight)
  33. sm_matrix *A;
  34. int *weight;
  35. {
  36.     register sm_row *best_row, *prow;
  37.     register sm_element *p;
  38.     int least_weight;
  39.     sm_row *save;
  40.     sm_matrix *B;
  41.     solution_t *indep;
  42.  
  43.     indep = solution_alloc();
  44.     B = build_intersection_matrix(A);
  45.  
  46.     while (B->nrows > 0) {
  47.     /*  Find the row which is disjoint from a maximum number of rows */
  48.     best_row = B->first_row;
  49.     for(prow = B->first_row->next_row; prow != 0; prow = prow->next_row) {
  50.         if (prow->length < best_row->length) {
  51.         best_row = prow;
  52.         }
  53.     }
  54.  
  55.     /* Find which element in this row has least weight */
  56.     if (weight == NIL(int)) {
  57.         least_weight = 1;
  58.     } else {
  59.         prow = sm_get_row(A, best_row->row_num);
  60.         least_weight = weight[prow->first_col->col_num];
  61.         for(p = prow->first_col->next_col; p != 0; p = p->next_col) {
  62.         if (weight[p->col_num] < least_weight) {
  63.             least_weight = weight[p->col_num];
  64.         }
  65.         }
  66.     }
  67.     indep->cost += least_weight;
  68.     (void) sm_row_insert(indep->row, best_row->row_num);
  69.  
  70.     /*  Discard the rows which intersect this row */
  71.     save = sm_row_dup(best_row);
  72.     for(p = save->first_col; p != 0; p = p->next_col) {
  73.         sm_delrow(B, p->col_num);
  74.         sm_delcol(B, p->col_num);
  75.     }
  76.     sm_row_free(save);
  77.     }
  78.  
  79.     sm_free(B);
  80.  
  81. /*
  82.     if (! verify_indep_set(A, indep->row)) {
  83.     fail("sm_maximal_independent_set: row set is not independent");
  84.     }
  85. */
  86.     return indep;
  87. }
  88.  
  89. static sm_matrix *
  90. build_intersection_matrix(A)
  91. sm_matrix *A;
  92. {
  93.     register sm_row *prow, *prow1;
  94.     register sm_element *p, *p1;
  95.     register sm_col *pcol;
  96.     sm_matrix *B;
  97.  
  98.     /* Build row-intersection matrix */
  99.     B = sm_alloc();
  100.     for(prow = A->first_row; prow != 0; prow = prow->next_row) {
  101.  
  102.     /* Clear flags on all rows we can reach from row 'prow' */
  103.     for(p = prow->first_col; p != 0; p = p->next_col) {
  104.         pcol = sm_get_col(A, p->col_num);
  105.         for(p1 = pcol->first_row; p1 != 0; p1 = p1->next_row) {
  106.         prow1 = sm_get_row(A, p1->row_num);
  107.         prow1->flag = 0;
  108.         }
  109.     }
  110.  
  111.     /* Now record which rows can be reached */
  112.     for(p = prow->first_col; p != 0; p = p->next_col) {
  113.         pcol = sm_get_col(A, p->col_num);
  114.         for(p1 = pcol->first_row; p1 != 0; p1 = p1->next_row) {
  115.         prow1 = sm_get_row(A, p1->row_num);
  116.         if (! prow1->flag) {
  117.             prow1->flag = 1;
  118.             (void) sm_insert(B, prow->row_num, prow1->row_num);
  119.         }
  120.         }
  121.     }
  122.     }
  123.  
  124.     return B;
  125. }
  126.